package DataStructure.heap;

public class HeapSort {
    //判断heap堆中i处的元素是否小于j处的元素
    private static boolean less(Comparable[] heap,int i,int j){
        return heap[i].compareTo(heap[j])<0;
    }

    //交换heap堆中i和j处的值
    private static void exch(Comparable[] heap,int i,int j){
        Comparable temp=heap[i];
        heap[i]=heap[j];
        heap[j]=temp;
    }

    //根据原数组source构造处堆heap
    private static void createHeap(Comparable[] source,Comparable[] heap){
        //把source中的元素拷贝到heap中，heap中的元素就形成了一个无序堆
        System.arraycopy(source,0,heap,1,source.length);
        //堆中元素做下沉调整，从长度的一半处往索引1处扫描
        for (int i = heap.length/2; i > 0; i--) {
            //下沉调整
            sink(heap,i,heap.length-1);
        }
    }


    //对source中的方法进行从小到大排序
    public static void sort(Comparable[] source){
        //构建堆
        Comparable[] heap = new Comparable[source.length + 1];
        createHeap(source,heap);//heap中存储的是无序的元素
        //记录未排序的元素中最大索引
        int N=heap.length-1;
        //通过循环，交换1索引处的元素和排序的元素中最大索引处的元素
        while (N!=1){
            //交换元素
            exch(heap,1,N);
            //排除交换后最大索引所在的索引，让他不要参与堆的下沉
            N--;
            //需要对1处的元素做下沉调整
            sink(heap,1,N);
        }
        //把heap的数据复制到source中
        System.arraycopy(heap,1,source,0,source.length);
    }

    //在heap中，对target处的元素做下沉，范围0-range
    private static void sink(Comparable[] heap,int target,int range){
        while (2*target<=range){
            //1.找出当前节点的较大的子节点
            int max;
            if(2*target+1<=range){
                if(less(heap,2*target,2*target+1)){
                    max=2*target+1;
                }else {
                    max=2*target;
                }
            }else {
                max=2*target;
            }
            //2.比较当前节点的值和较大子节点的值
            if(!less(heap,target,max)){
                break;
            }
            exch(heap,target,max);
            target=max;
        }
    }


}
